package class03;

import java.util.Arrays;

/**
 * @description: 面试题：假设有一个数组arr,长度为N,现将它一分为2,并且保证两端都有数
 *              设计一种算法使得 |max(左部分) - max(右部分)| 尽可能大,并返回该最大值
 * @time: 2021/7/7 11:23
 * @author: lhy
 */
public class MaxLeftMaxRight {

    public static int solution(int[] arr){
        if (arr == null || arr.length < 2){
            return -1;
        }
        int max = arr[0];
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            max = Math.max(max,arr[i]);
        }
        return max - Math.min(arr[0],arr[n-1]);
    }

    public static int test(int[] arr){
        if (arr == null || arr.length < 2){
            return -1;
        }
        int ans = Integer.MIN_VALUE;
        int n = arr.length;
        for (int leftEnd = 0; leftEnd < n - 1; leftEnd++) {
            int leftMax = arr[0];
            for (int i = 0; i <= leftEnd; i++) {
                leftMax = Math.max(leftMax, arr[i]);
            }
            int rightMax = arr[leftEnd + 1];
            for (int i = leftEnd + 2; i < n; i++) {
                rightMax = Math.max(rightMax,arr[i]);
            }
            ans = Math.max(ans,Math.abs(leftMax - rightMax));
        }
        return ans;
    }

    public static int[] generateRandomArray(int maxLen, int maxValue){
        int len = (int) (Math.random() * (maxLen + 1));
        int[] arr = new int[len];
        for (int i = 0; i < len; i++) {
            arr[i] = (int) (Math.random() * (maxValue + 1)) - (int) (Math.random() * (maxValue + 1));
        }
        return arr;
    }
    public static void main(String[] args) {
        int testTimes = 10000;
        int maxLen = 2000;
        int maxValue = 1000;
        System.out.println(">>>Test start...");
        for (int i = 0; i < testTimes; i++) {
            int[] arr = generateRandomArray(maxLen,maxValue);
            int ans1 = solution(arr);
            int ans2 = test(arr);
            if (ans1 != ans2){
                System.out.println("Error!");
                System.out.println("Array:" + Arrays.toString(arr));
                System.out.println("solutionAns: " + ans1 + "\nTestAns: " + ans2);
                break;
            }
        }
        System.out.println(">>>Test end.");
    }
}
